package com.example.spring;

import java.util.LinkedList;
import java.util.Queue;

public class StackWithTwoQueues {
    private Queue<Integer> queue1;
    private Queue<Integer> queue2;

    public StackWithTwoQueues() {
        queue1 = new LinkedList<>();
        queue2 = new LinkedList<>();
    }

    // 入栈操作
    public void push(int item) {
        // 总是将新元素添加到非空队列中
        if (!queue1.isEmpty()) {
            queue1.add(item);
        } else {
            queue2.add(item);
        }
    }

    // 出栈操作
    public int pop() {
        if (isEmpty()) {
            throw new RuntimeException("Stack is empty");
        }

        // 确定哪个队列是非空的
        Queue<Integer> nonEmptyQueue = queue1.isEmpty() ? queue2 : queue1;
        Queue<Integer> emptyQueue = queue1.isEmpty() ? queue1 : queue2;

        // 将非空队列中的元素（除了最后一个）转移到空队列
        while (nonEmptyQueue.size() > 1) {
            emptyQueue.add(nonEmptyQueue.remove());
        }

        // 最后一个元素就是栈顶元素
        return nonEmptyQueue.remove();
    }

    // 查看栈顶元素
    public int peek() {
        if (isEmpty()) {
            throw new RuntimeException("Stack is empty");
        }

        Queue<Integer> nonEmptyQueue = queue1.isEmpty() ? queue2 : queue1;
        Queue<Integer> emptyQueue = queue1.isEmpty() ? queue1 : queue2;

        int topElement = 0;
        while (!nonEmptyQueue.isEmpty()) {
            topElement = nonEmptyQueue.remove();
            emptyQueue.add(topElement);
            if (nonEmptyQueue.isEmpty()) {
                break;
            }
        }

        return topElement;
    }

    // 判断栈是否为空
    public boolean isEmpty() {
        return queue1.isEmpty() && queue2.isEmpty();
    }

    // 获取栈的大小
    public int size() {
        return queue1.size() + queue2.size();
    }

    public static void main(String[] args) {
        StackWithTwoQueues stack = new StackWithTwoQueues();

        stack.push(1);
        stack.push(2);
        stack.push(3);

        System.out.println(stack.pop());  // 输出3
        System.out.println(stack.peek()); // 输出2
        stack.push(4);
        System.out.println(stack.pop());  // 输出4
        System.out.println(stack.pop());  // 输出2
        System.out.println(stack.pop());  // 输出1
        System.out.println(stack.isEmpty()); // 输出true
    }
}